翻訳と辞書
Words near each other
・ "O" Is for Outlaw
・ "O"-Jung.Ban.Hap.
・ "Ode-to-Napoleon" hexachord
・ "Oh Yeah!" Live
・ "Our Contemporary" regional art exhibition (Leningrad, 1975)
・ "P" Is for Peril
・ "Pimpernel" Smith
・ "Polish death camp" controversy
・ "Pro knigi" ("About books")
・ "Prosopa" Greek Television Awards
・ "Pussy Cats" Starring the Walkmen
・ "Q" Is for Quarry
・ "R" Is for Ricochet
・ "R" The King (2016 film)
・ "Rags" Ragland
・ ! (album)
・ ! (disambiguation)
・ !!
・ !!!
・ !!! (album)
・ !!Destroy-Oh-Boy!!
・ !Action Pact!
・ !Arriba! La Pachanga
・ !Hero
・ !Hero (album)
・ !Kung language
・ !Oka Tokat
・ !PAUS3
・ !T.O.O.H.!
・ !Women Art Revolution


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

prune and search : ウィキペディア英語版
prune and search
Prune and search is a method of solving optimization problems suggested by Nimrod Megiddo in 1983. 〔N. Megiddo. Linear-time algorithms for linear programming in R3 and related problems. SIAM J. Computing, 12:759–776, 1983.〕
The basic idea of the method is a recursive procedure in which at each step the input size is reduced ("pruned") by a constant factor 0 < ''p'' < 1. As such, it is a form of decrease and conquer algorithm, where at each step the decrease is by a constant factor. Let n be the input size, ''T''(''n'') be the time complexity of the whole prune-and-search algorithm, S(n) is the time complexity of the pruning step, then ''T''(''n'') obeys the following recurrence relation:
: T(n) = S(n) + T(n(1-p)), \,
which has the solution ''T''(''n'') = O(''S''(''n'')), since summing a geometric series only multiplies by a constant factor, namely 1/(1-(1-p)) = 1/p.
In particular, Megiddo himself used this approach in his linear time algorithm for the linear programming problem when the dimension is fixed〔Nimrod Megiddo, Linear Programming in Linear Time When the Dimension Is Fixed, 1984〕 and for the minimal enclosing sphere problem for a set of points in space.〔
==References==


抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「prune and search」の詳細全文を読む



スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.